package br.ufcg.edu.algoritimo;

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Stack;

import br.ufcg.edu.algoritimo.No.COR;
import br.ufcg.edu.util.Constantes;

public class Huffman {
	
	public Huffman() {
	}

	public PriorityQueue<No> construirListaOrdenadaDeNos(
			List<No> folhas) {
		PriorityQueue<No> nos = new PriorityQueue<No>();

		for (No no : folhas) {
			nos.add(no);
		}

		return nos;
	}

	public No construirArvore(List<No> caracteres) {
		PriorityQueue<No> carecteresQueue = construirListaOrdenadaDeNos(caracteres);

		while (carecteresQueue.size() > 1) {
			No primeiroMenor = carecteresQueue.poll();
			No segundoMenor = carecteresQueue.poll();

			No resultante = mergeNos(segundoMenor, primeiroMenor);

			carecteresQueue.add(resultante);
		}

		return carecteresQueue.poll();
	}

	private No mergeNos(No atual, No proximo) {
		int valor = atual.getValor() + proximo.getValor();
		Character descricao = Constantes.DESCRICAO_NO_ITERNO;

		return new No(atual, proximo, valor, descricao);
	}

	public Map<Character, String> criarMapeamento(No no) {
		Map<Character, String> mapeamento = new HashMap<Character, String>();

		Stack<Character> prefixos = new Stack<Character>();
		Stack<No> pilhaDeNos = new Stack<No>();
		prefixos.add(' ');
		pilhaDeNos.add(no);
		while (!pilhaDeNos.isEmpty()) {
			No no_atual = pilhaDeNos.peek();
			no_atual.setCor(COR.CINZA);
			if (no_atual.isFolha()) {
				mapeamento.put(no_atual.getDescricao(),
						imprimeprefixos(prefixos));
				removeNo(prefixos, pilhaDeNos);
			
			} else {
				if (no_atual.getEsquerda() != null
						&& no_atual.getEsquerda().getCor() == COR.BRANCO) {
					pilhaDeNos.add(no_atual.getEsquerda());
					prefixos.add('0');
				
				} else if (no_atual.getDireita() != null
						&& no_atual.getDireita().getCor() == COR.BRANCO) {
					pilhaDeNos.add(no_atual.getDireita());
					prefixos.add('1');
				
				} else {
					removeNo(prefixos, pilhaDeNos);
				}
			}
		}

		return mapeamento;
	}

	private void removeNo(Stack<Character> prefixos,
			Stack<No> pilhaDeNos) {
		pilhaDeNos.pop();
		prefixos.pop();
	}

	private String imprimeprefixos(Stack<Character> prefixos) {
		StringBuilder retorno = new StringBuilder();
		for (int i = 1; i < prefixos.size(); i++) {
			retorno.append(prefixos.get(i));
		}
		return retorno.toString();
	}

}
